#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    Solution(int a[], int n) {

    }

    int kthLargest(TreeNode* root, int k) {
        TreeNode* curNode = root;
        TreeNode* predecessor = NULL;
        int res = 0;

        while (curNode != NULL) {
            if (k == 0)
                break;
            // 此处如果break，整棵树的结构发生了改变，这是不可以的，所以morris算法要求一定要完成一边遍历才行
            if (curNode->right == NULL) {
                res = curNode->val;
                k--;
                curNode = curNode->left;
            }
            else {
                predecessor = curNode->right;
                while (predecessor->left != NULL && predecessor->left != curNode)
                    predecessor = predecessor->left;
                if (predecessor->left == NULL) {
                    predecessor->left = curNode;
                    curNode = curNode->right;
                }
                else {
                    res = curNode->val;
                    k--;
                    predecessor->left = NULL;
                    curNode = curNode->left;
                }
            }
        }
        
        return res;
    }
};


int main() {

}